1. Field of Invention
The present invention relates to a network switch. More particularly, the present invention relates to a switch controller capable of easing flow congestion in a network.
2. Description of Related Art
Ethernet is probably the most widely used local area network (LAN) in electronic communication. However, due to a data transmission rate of mere 10 Mbps, a conventional Ethernet can hardly transmit the vast quantity of data flow required in a multi-media system. Consequently, a faster Ethernet system having a data transmission rate of 100 Mbps called Fast Ethernet appears. In the Fast Ethernet design, a reconciliation sublayer is introduced between a medium access control (MAC) sublayer and a physical medium dependency (PMD) sublayer. To use the Fast Ethernet system, the network interface card in each network workstation has to be replaced by a 100 Mbps fast Ethernet interface card. The network interface card in each workstation can also be retained, however, a switch device must be employed. In fact, in order to retain the original network interface card in each workstation, the 10 Mbps Ethernet equipment formerly invested by a company can be incorporated into the Fast Ethernet network through the switch device.
A workstation with a conventional Ethernet utilizing a twisted pair, disregarding whether the data transmission rate is 10 Mbps or 100 Mbps, is connected to a server via an Ethernet hub. In general, the bandwidth of an Ethernet hub is normally shared by all the workstations connected to the network. For example, for a 16 port 100 Mbps Ethernet hub, if four workstations are connected to the network, the bandwidth is shared between four workstations. On the other hand, if each of the 16 ports is connected to a workstation, the bandwidth is shared between all sixteen workstations. As the number of network user increases, the number of collisions in the network increases proportionately. Hence, network bandwidth for each user decreases while users increase. In a multimedia-craved world, a conventional Ethernet hub can not meet the traffic demanded by booming users.
The switch device intends to improve data flow so that each of the workstations connected to the device is able to enjoy faster data transmission. To achieve correct data switching, the switch device must register various connections between each workstation and each port. In other words, the switch device must have a module for recording all the addresses in a way similar to a bridging device. When the switch device receives a frame, the device will consult a path lookup table to find the port of the target workstation. If the target workstation is found, a controller will send out a control signal to the switch element and redirecting the frame to the port. On the contrary, if the target workstation is not found, the frame is broadcast to all the ports just to ensure that the target workstation is able to receive this frame.
The institute of electrical & electronics engineering (IEEE) has recently provided a standard specification 802.3u for network management 802.3u capable of simplifying network management. The IEEE standard 802.3u introduces an ‘auto-negotiation’ function, also known as an N-way function. The ‘auto-negotiation’ function enables the switch device and the Ethernet interface card of a workstation to learn each others' state, which may have various combinations as shown in Table I. An N-way switch device can learn the data transmission rate (10 Mbps or 100 Mbps) and multiplexing mode (full duplex or half-duplex) for each Ethernet interface card to employ a proper congestion control mechanism.
Before ‘auto-negotiation’ strategy is incorporated into standard specification 802.3u of IEEE, a few manufacturers has already produced Ethernet card that has auto-sensing capability. A number of switch devices and Ethernet cards are shown in Table 1, some of the devices has auto-negotiation functions while some has not.
TABLE 1various combinations of states between an Ethernet hub (switch device) andEthernet card with or without ‘auto-negotiation’ like function and operation thereof.Support onlySupport onlyNew generation 10/100TXNew generation of auto-10BASE-T hub100BASE-T hubco-existent network andnegotiation 10/100TX co-(switch device)(switch device)hub (switch device)existent hub (switch device)Support only10 MbpsChange to a 100 MbpsManual switch of the hubAutomatic switching of hub10BASE-T network cardnetwork card(switch device) to 10 Mbps(switch device) to 10 MbpsNetwork card withAutomatic switch ofAutomatic switch ofAutomatic switch ofManual switch of hubnon-standard auto-network card to 10 Mbpsnetwork card to 100 Mbpsnetwork card to 100 Mbps(switch device) andsensing capabilityafter manual switch of hubnetwork card to 100 Mbps(switch device) to 100 Mbps10/100TX co-existentAutomatic switch ofAutomatic switch ofManual switch of hubAutomatic switch of hubnetwork card with newnetwork card to 10 Mbpsnetwork card to 100 Mbps(switch device) and(switch device) andgeneration auto-half-duplexnetwork card to 100 Bbpsnetwork card to 100 Mbpsnegotiation capability
Due to the rapid progress in semiconductor technologies, the difference in the cost of producing a switch device and an Ethernet hub is getting smaller. Because of many advantages of a switch device, Ethernet hubs are gradually replaced by switch devices. Moreover, since a switch device can perform the functions provided by an Ethernet hub, combinations of devices detailed in Table 1 are all applicable to switch devices.
Furthermore, due to the multiplicity of transmission modes among different Ethernet devices, the automatic-negotiation relies on a set of priority sequence registered in a table to ensure the selection of an optimal transmission mode between two Ethernet devices. For example, a 10/100 Mbps dual speed network card is capable of operating at 10 Mbps or 100 Mbps. Under the priority algorithm, the priority sequence table preferably selects 100 Mbps. Table 2 is a priority setting for the different transmission modes for Ethernet devices having auto-negotiation capability.
TABLE 2Priority setting of Ethernet devices with auto-negotiation capabilityPriorityExplanations1100BASE-T2 full duplex2100BASE-T23100BASE-TX full duplex4100BASE-T45100BASE-TX610BASE-T full duplex710BASE-T
In Table 2, full duplex transmission mode has a higher priority than half-duplex mode because full duplex has a much higher data transmission rate than half-duplex. Transmission mode 10BASE-T has the least priority because it has the slowest data transmission rate. By consulting the priority table 2, the most suitable mode for transmitting data between the switch device (hub) and the network card can be selected.
To increase the overall throughput after the best transmission mode is chosen, the switch device usually provides a congestion control mechanism for transmitting information packets among the transmission ports. According to the resulting auto-negotiation between the target device (for example, an network card) and the switch device, one of the following three congestion control modes are adopted: (1) When the target device has full-duplex transmission capacity and flow control capability, the switch device will opt for a flow control mode; (2) when the target device has full-duplex transmission capacity but no flow control capability, the switch device will opt for a drop control mode; and (3) when the target device has neither half-duplex transmission capacity nor flow control capability, the switch device will opt for a back-pressure control mode. In the backpressure control mode, the switch controller issues a collision signal to destroy an incoming packet. On detecting the collision, the workstation will branch into a binary exponential backoff algorithm to compute a waiting time before the packet is submitted again. In the drop control mode, the packet is directly dropped at the source port instead of sending to the congested target port. This is because the target device uses full duplex transmission and different transmission lines are used respectively for sending and receiving data. Further, the source port enters a flow control mode whenever the target port is congested. In subsequent stage, flow control windows (XOFF windows) are triggered. Once XOFF windows are triggered, the switch controller will control the flow of packets according to the number of free buffers present.
The congestion control method in a conventional switch controller has the following two drawbacks:
(1) The ports of a switch controller have a plurality of input buffers. Furthermore, a plurality of private buffers are reserved by the input terminals of the ports for private use. However, when the number of free output buffers in the port of the switch controller is insufficient, the deployment of buffers by other ports is not permitted. Hence, the capacity of the switch device is limited.
(2) The XOFF threshold value of the flow control window is fixed. Hence, the switch device is unable to adjust the XOFF threshold value dynamically according to the number of free buffers. Therefore, the management of shared memory in the switch controller can not achieve the best performance.
FIG. 1 is a block diagram showing the electrical connections in a conventional switch device. The switch device 100 in FIG. 1 has a plurality of ports (eight ports are shown in FIG. 1). Each port is connected to a physical layer device 130. A static random access memory (SRAM) 120 is provided in the Ethernet control device 110 serving as a shared memory or buffer. On receiving a network packet, the port transfers and stores the packet in the shared buffer until the packet is retrieved by a target port.
FIG. 2 is a diagram showing the congestion control mechanism for resolving congestion in a conventional switch controller. When both the switch device and the network card can operate in full duplex mode and have flow control capability, flow control mode is called upon to resolve network congestion problems. While testing the performance of switch controller, there is an item known as head of line blocking (HOL). As shown in FIG. 2, head of line blocking refers to the blocking of the output of a port in the switch controller due to occupation so that other ports is unable to function normally. For example, assume that all ports are capable of transmitting data at 100 Mbps. When port 2 transmits data at 100% bandwidth to the port 3 while port 0 also transmits data at 50% bandwidth to the port 3, the total amount of data transmitted to port 3 is 150 Mbps. Hence, the amount of data going to the port 3 exceeds its admissible limit. Consequently, some packets may accumulate in the output queues of the port 3. In the meantime, if the port 4 needs to transmit data at 100% bandwidth to port 5, the transmission fails because all the free buffers are occupied due to the heavy congestion at port 3. Therefore, head of line blocking is a major factor affecting the efficiency of the switch controller.
In this invention, a number of private buffers are reserved for each port. Thus, although the port 3 is heavily congested, data transmission between port 4 and port 5 can still carry on because the port 5 has private buffer space.